This paper studies the tradeoffs between reopening and not reopening nodes in the context of Weighted A*. A straightforward intuitive scenario is that reopening nodes results in finding shorter solutions than not reopening nodes, at the cost of expanding more nodes. In this paper we classify all possibile tendencies and show an example graph where different tendencies are evident only by varying the W parameter of WA* and without changing the structure of the graph. We then experimentally demonstrate the different tendencies on a number of domains. Finally, we provide experimental support that intelligent reopening polices might lead to better performance. This is a work in progress and we discuss several future directions.

The paper explores the potential of look-ahead methods within the context of AND/OR search in graphical models using the Mini-Bucket heuristic for combinatorial optimization tasks (e.g., weighted CSPS or MAP inference). We study how these methods can be used to compensate for the approximation error of the initially generated Mini-Bucket heuristics, within the context of anytime Branch-And-Bound search.